package io.zhengsh.vvip.leetcode.recall;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q40_combination_sum_ii {

    public static void main(String[] args) {

    }

    static class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            int len = candidates.length;
            List<List<Integer>> list = new ArrayList<>();
            if (len == 0) {
                return list;
            }
            // 排序
            Arrays.sort(candidates);

            dfs(candidates, len, 0, target, new ArrayDeque<Integer>(), list);
            return list;
        }

        /**
         * @param candidates 候选数组
         * @param len        数组长度
         * @param i          从候选数组的 i 位置开始搜索
         * @param target     剩余值
         * @param cob        根节点到叶子节点的路径
         * @param res        返回结果
         */
        private void dfs(int[] candidates, int len, int i, int target, ArrayDeque<Integer> cob, List<List<Integer>> res) {

            if (target == 0) {
                res.add(new ArrayList<Integer>(cob));
                return;
            }
            for (int j = i; j < len; j++) {
                if (target - candidates[j] < 0) {
                    break;
                }

                if (j > i && candidates[j] == candidates[j - 1]) {
                    continue;
                }
                cob.addLast(candidates[j]);

                dfs(candidates, len, j + 1, target - candidates[j], cob, res);

                cob.removeLast();
            }
        }
    }
}
